SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Time complexity</title>

</head>

Time complexity

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">"Running time" redirects here; not to be confused with <a href="Running_Time_(film)" title="Running Time (film)">Running Time (film)</a>.</div>

In <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, the time complexity is the <a href="Computational_complexity" title="Computational complexity">computational complexity</a> that describes the amount of computer time it takes to run an <a href="Algorithm" title="Algorithm">algorithm</a>. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a <a href="Constant_factor" class="mw-redirect" title="Constant factor">constant factor</a>.

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the <a href="Worst-case_complexity" title="Worst-case complexity">worst-case time complexity</a>, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the <a href="Average-case_complexity" title="Average-case complexity">average-case complexity</a>, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expressed as a <a href="Function_(mathematics)" title="Function (mathematics)">function</a> of the size of the input.<a href="#cite_note-Sipser-1">[1]</a>: 226 Since this function is generally difficult to compute exactly, and the running time for small inputs is usually not consequential, one commonly focuses on the behavior of the complexity when the input size increases—that is, the <a href="Asymptotic_analysis" title="Asymptotic analysis">asymptotic behavior</a> of the complexity. Therefore, the time complexity is commonly expressed using <a href="Big_O_notation" title="Big O notation">big O notation</a>, typically <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{\alpha })}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{\alpha })}</annotation>

</semantics>

</math><img src="./cec66a4a63247dd112a6ec9dd8eae41909e6b300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.261ex; height:2.843ex;" alt="{\displaystyle O(n^{\alpha })}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(2^{n})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(2^{n})}</annotation>

</semantics>

</math><img src="./d4b1a4ff0bc4f81ebf79f28260c6fb54ee08ff8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.964ex; height:2.843ex;" alt="{\displaystyle O(2^{n})}" loading="lazy">, etc., where n is the size in units of <a href="Bit" title="Bit">bits</a> needed to represent the input.

Algorithmic complexities are classified according to the type of function appearing in the big O notation. For example, an algorithm with time complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> is a linear time algorithm and an algorithm with time complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{\alpha })}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{\alpha })}</annotation>

</semantics>

</math><img src="./cec66a4a63247dd112a6ec9dd8eae41909e6b300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.261ex; height:2.843ex;" alt="{\displaystyle O(n^{\alpha })}" loading="lazy"> for some constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha >0}</annotation>

</semantics>

</math><img src="./edd4f784b6e8bb68fa774213ceacbab2d97825dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.749ex; height:2.176ex;" alt="{\displaystyle \alpha >0}" loading="lazy"> is a polynomial time algorithm.

<div class="mw-heading mw-heading2"><h2 id="Table_of_common_time_complexities">Table of common time complexities</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Computational_complexity_of_mathematical_operations" title="Computational complexity of mathematical operations">Computational complexity of mathematical operations</a></div>

The following table summarizes some classes of commonly encountered time complexities. In the table, poly(x) = xO(1), i.e., polynomial in x.

<th><a href="Complexity_class" title="Complexity class">Complexity class</a></th>

<th>Time complexity (O(n))</th>

<th>Examples of running times</th>

<th>Example algorithms

</th></tr>

<tr>

<td>constant time</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"></td>

<td>Finding the median value in a sorted <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a> of numbers. Calculating (−1)n.

</td></tr>

<tr>

<td><a href="Inverse_Ackermann_function" class="mw-redirect" title="Inverse Ackermann function">inverse Ackermann</a> time</td>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O{\bigl (}\alpha (n){\bigr )}}</annotation>

</semantics>

</math><img src="./6325c00a7a6fdf5b3b05022c56d09054db68e156.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.595ex; height:3.176ex;" alt="{\displaystyle O{\bigl (}\alpha (n){\bigr )}}" loading="lazy"></td>

<td><a href="Amortized_time" class="mw-redirect" title="Amortized time">Amortized time</a> per operation using a <a href="Disjoint_set_data_structure" class="mw-redirect" title="Disjoint set data structure">disjoint set</a>

</td></tr>

<tr>

<td><a href="Iterated_logarithm" title="Iterated logarithm">iterated logarithmic</a> time</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{*}n)}</annotation>

</semantics>

</math><img src="./ba846ca61ce56540d44c487534367163945ad17d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.39ex; height:2.843ex;" alt="{\displaystyle O(\log ^{*}n)}" loading="lazy"></td>

<td><a href="Cole-Vishkin_algorithm" class="mw-redirect" title="Cole-Vishkin algorithm">Distributed coloring of cycles</a>

</td></tr>

<tr>

<td>log-logarithmic</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log \log n)}</annotation>

</semantics>

</math><img src="./a9f3ded7e013a35c8039ff3276bee6e183d7f1a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.695ex; height:2.843ex;" alt="{\displaystyle O(\log \log n)}" loading="lazy"></td>

<td>Amortized time per operation using a bounded <a href="Priority_queue" title="Priority queue">priority queue</a><a href="#cite_note-2">[2]</a>

</td></tr>

<tr>

<td>logarithmic time</td>

<td><a href="DLOGTIME" title="DLOGTIME">DLOGTIME</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log n}</annotation>

</semantics>

</math><img src="./317ab5292da7c7935aec01a570461fe0613b21d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.754ex; height:2.509ex;" alt="{\displaystyle \log n}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log(n^{2})}</annotation>

</semantics>

</math><img src="./a8bbd9e54f53c3999490142142fc6282e21eaf42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.23ex; height:3.176ex;" alt="{\displaystyle \log(n^{2})}" loading="lazy"></td>

<td><a href="Binary_search" title="Binary search">Binary search</a>

</td></tr>

<tr>

<td>polylogarithmic time</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\textsf {poly}}(\log n)}</annotation>

</semantics>

</math><img src="./27086639d6d36afd33dd17fe6174ed280e037707.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.555ex; height:2.843ex;" alt="{\displaystyle {\textsf {poly}}(\log n)}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\log n)^{2}}</annotation>

</semantics>

</math><img src="./d5e8b416ed664f6e00aae39e3d275f82839adea0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.617ex; height:3.176ex;" alt="{\displaystyle (\log n)^{2}}" loading="lazy"></td>

<td>

</td></tr>

<tr>

<td>fractional power</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{c})}</annotation>

</semantics>

</math><img src="./949acd060374f98c6dc5f76ad962c7fe2d6636d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.922ex; height:2.843ex;" alt="{\displaystyle O(n^{c})}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0<c<1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0<c<1}</annotation>

</semantics>

</math><img src="./7c2ef66b35dc03fb20aa2da7cf53cdaaaac18ad0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.529ex; height:2.176ex;" alt="{\displaystyle 0<c<1}" loading="lazy"></td>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{\frac {1}{2}}}</annotation>

</semantics>

</math><img src="./cde54d7624bc2445a98cb673278df108b48cc786.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.13ex; height:3.509ex;" alt="{\displaystyle n^{\frac {1}{2}}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{\frac {2}{3}}}">

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{\frac {2}{3}}}</annotation>

</semantics>

</math><img src="./e6da2424ef7834dd547c2aac35892595cd112846.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.13ex; height:3.509ex;" alt="{\displaystyle n^{\frac {2}{3}}}" loading="lazy"></td>

<td><a href="Range_searching" title="Range searching">Range searching</a> in a <a href="K-d_tree" title="K-d tree">k-d tree</a>

</td></tr>

<tr>

<td>linear time</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2n+5}</annotation>

</semantics>

</math><img src="./988be5c38cac9e34f9d6a9b180f26193ece9f41e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.56ex; height:2.343ex;" alt="{\displaystyle 2n+5}" loading="lazy"></td>

<td>Finding the smallest or largest item in an unsorted <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a>. <a href="Kadane's_algorithm" class="mw-redirect" title="Kadane's algorithm">Kadane's algorithm</a>. <a href="Linear_search" title="Linear search">Linear search</a>.

</td></tr>

<tr>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log ^{*}n)}</annotation>

</semantics>

</math><img src="./9c6a679f4e6f08c50bfbdf85386ff72f320fc384.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.172ex; height:2.843ex;" alt="{\displaystyle O(n\log ^{*}n)}" loading="lazy"></td>

<td><a href="Raimund_Seidel" title="Raimund Seidel">Seidel</a>'s <a href="Polygon_triangulation" title="Polygon triangulation">polygon triangulation</a> algorithm.

</td></tr>

<tr>

<td>linearithmic time</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\log n}</annotation>

</semantics>

</math><img src="./560dfdce0353a330e03e4b3e0b7ca6e484bb40fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.535ex; height:2.509ex;" alt="{\displaystyle n\log n}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log n!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log n!}</annotation>

</semantics>

</math><img src="./331273b9c429c44271590e75da654b7b60c3194c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.4ex; height:2.509ex;" alt="{\displaystyle \log n!}" loading="lazy"></td>

<td>Fastest possible <a href="Comparison_sort" title="Comparison sort">comparison sort</a>. <a href="Fast_Fourier_transform" title="Fast Fourier transform">Fast Fourier transform</a>.

</td></tr>

<tr>

<td>quasilinear time</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n{\textsf {poly}}(\log n)}</annotation>

</semantics>

</math><img src="./137ea62cea10e9bc0a326a3829f97fe4c4a88ea2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.95ex; height:2.843ex;" alt="{\displaystyle n{\textsf {poly}}(\log n)}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\log ^{2}n}</annotation>

</semantics>

</math><img src="./8dcc3d3ab4d647731efd75119a13e8febd1a7e44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.59ex; height:3.009ex;" alt="{\displaystyle n\log ^{2}n}" loading="lazy"></td>

<td><a href="Polynomial_evaluation#Multipoint_evaluation" title="Polynomial evaluation">Multipoint polynomial evaluation</a>

</td></tr>

<tr>

<td>quadratic time</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}}</annotation>

</semantics>

</math><img src="./ac9810bbdafe4a6a8061338db0f74e25b7952620.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.449ex; height:2.676ex;" alt="{\displaystyle n^{2}}" loading="lazy"></td>

<td><a href="Bubble_sort" title="Bubble sort">Bubble sort</a>. <a href="Insertion_sort" title="Insertion sort">Insertion sort</a>. <a href="Convolution_theorem" title="Convolution theorem">Direct convolution</a>

</td></tr>

<tr>

<td>cubic time</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{3})}</annotation>

</semantics>

</math><img src="./6b04f5c5cfea38f43406d9442387ad28555e2609.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{3})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{3}}</annotation>

</semantics>

</math><img src="./3e9d1a52e455a7a5272a345b2697e35f1579b681.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.449ex; height:2.676ex;" alt="{\displaystyle n^{3}}" loading="lazy"></td>

<td>Naive multiplication of two <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\times n}</annotation>

</semantics>

</math><img src="./59d2b4cb72e304526cf5b5887147729ea259da78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.63ex; height:1.676ex;" alt="{\displaystyle n\times n}" loading="lazy"> matrices. Calculating <a href="Partial_correlation" title="Partial correlation">partial correlation</a>.

</td></tr>

<tr>

<td>polynomial time</td>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{O(\log n)}={\textsf {poly}}(n)}</annotation>

</semantics>

</math><img src="./06fdb415ff47d4aca7e3edf9e8fa7eb431a3c6ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.698ex; height:3.343ex;" alt="{\displaystyle 2^{O(\log n)}={\textsf {poly}}(n)}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}+n}</annotation>

</semantics>

</math><img src="./bc5a79f894693cebbe2030d2e3daa35a7e5cd9cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.684ex; height:2.843ex;" alt="{\displaystyle n^{2}+n}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{10}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{10}}</annotation>

</semantics>

</math><img src="./df654a91adfed0cbf842309de83715d2eb41ce0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.271ex; height:2.676ex;" alt="{\displaystyle n^{10}}" loading="lazy"></td>

<td><a href="Karmarkar's_algorithm" title="Karmarkar's algorithm">Karmarkar's algorithm</a> for <a href="Linear_programming" title="Linear programming">linear programming</a>. <a href="AKS_primality_test" title="AKS primality test">AKS primality test</a><a href="#cite_note-tao-aks-3">[3]</a><a href="#cite_note-4">[4]</a>

</td></tr>

<tr>

<td>quasi-polynomial time</td>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{{\textsf {poly}}(\log n)}}</annotation>

</semantics>

</math><img src="./5366b3c6cb94ac2ea687b435f40657b48c0499a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.972ex; height:2.843ex;" alt="{\displaystyle 2^{{\textsf {poly}}(\log n)}}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{\log \log n}}</annotation>

</semantics>

</math><img src="./39561b8c2b523322a75d097915035e8fca3811b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.59ex; height:2.676ex;" alt="{\displaystyle n^{\log \log n}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{\log n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{\log n}}</annotation>

</semantics>

</math><img src="./c403a7c02eceb7217e79eafa65de2554c56ebb02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.102ex; height:2.676ex;" alt="{\displaystyle n^{\log n}}" loading="lazy"></td>

<td>Best-known O(log2n)-<a href="Approximation_algorithm" title="Approximation algorithm">approximation algorithm</a> for the directed <a href="Steiner_tree_problem" title="Steiner tree problem">Steiner tree problem</a>, best known <a href="Parity_game" title="Parity game">parity game</a> solver,<a href="#cite_note-5">[5]</a> best known <a href="Graph_isomorphism" title="Graph isomorphism">graph isomorphism</a> algorithm

</td></tr>

<tr>

<td>sub-exponential time (first definition)</td>

<td>SUBEXP</td>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(2^{n^{\epsilon }})}</annotation>

</semantics>

</math><img src="./b70ad01996d0c0c0b7274da0854edf54ecebf8f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.67ex; height:3.176ex;" alt="{\displaystyle O(2^{n^{\epsilon }})}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0<\epsilon <1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0<\epsilon <1}</annotation>

</semantics>

</math><img src="./36ed9547541a6736e0d2a979e8ae3f4a2c1193c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.466ex; height:2.176ex;" alt="{\displaystyle 0<\epsilon <1}" loading="lazy"></td>

<td>Contains <a href="Bounded-error_probabilistic_polynomial" class="mw-redirect" title="Bounded-error probabilistic polynomial">BPP</a> unless EXPTIME (see below) equals <a href="Arthur%E2%80%93Merlin_protocol#MA" title="Arthur–Merlin protocol">MA</a>.<a href="#cite_note-bpp-6">[6]</a>

</td></tr>

<tr>

<td>sub-exponential time (second definition)</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{o(n)}}</annotation>

</semantics>

</math><img src="./98ee27d18f582367c1c737ddc1c3380a92c93c0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.458ex; height:2.843ex;" alt="{\displaystyle 2^{o(n)}}" loading="lazy"></td>

<msup>

<mroot>

</mrow>

</mroot>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{\sqrt[{3}]{n}}}</annotation>

</semantics>

</math><img src="./55eec9753eb9a7bc49aa7e4ccac33f66844fe645.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.75ex; height:3.176ex;" alt="{\displaystyle 2^{\sqrt[{3}]{n}}}" loading="lazy"></td>

<td><a href="General_number_field_sieve" title="General number field sieve">Best classical algorithm</a> for <a href="Integer_factorization" title="Integer factorization">integer factorization</a>

formerly-best algorithm for <a href="Graph_isomorphism_problem" title="Graph isomorphism problem">graph isomorphism</a>

</td></tr>

<tr>

<td>exponential time (with linear exponent)</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{O(n)}}</annotation>

</semantics>

</math><img src="./69a16bd3fa1209d0c3a221916283c9c3a4006d33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.914ex; height:2.843ex;" alt="{\displaystyle 2^{O(n)}}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1.1^{n}}</annotation>

</semantics>

</math><img src="./5b4386d7093a0147839223c0f43e5249aeaa6e38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.19ex; height:2.343ex;" alt="{\displaystyle 1.1^{n}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 10^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 10^{n}}</annotation>

</semantics>

</math><img src="./eeff06a7c9ad9455cb809047cfc97a92c51e1bf7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.543ex; height:2.343ex;" alt="{\displaystyle 10^{n}}" loading="lazy"></td>

<td>Solving the <a href="Traveling_salesman_problem" class="mw-redirect" title="Traveling salesman problem">traveling salesman problem</a> using <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a>

</td></tr>

<tr>

<td>factorial time</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)!=2^{O(n\log n)}}</annotation>

</semantics>

</math><img src="./fb5847f828b512de7a23f83dd2cf50f853dd6ec8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.499ex; height:3.343ex;" alt="{\displaystyle O(n)!=2^{O(n\log n)}}" loading="lazy"></td>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n!,n^{n},2^{n\log n}}</annotation>

</semantics>

</math><img src="./f7783be21cc51bae90c5cd232d5ba10f87de5111.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.965ex; height:3.009ex;" alt="{\displaystyle n!,n^{n},2^{n\log n}}" loading="lazy"></td>

<td>Solving the <a href="Travelling_salesman_problem" title="Travelling salesman problem">traveling salesman problem</a> via <a href="Brute-force_search" title="Brute-force search">brute-force search</a>

</td></tr>

<tr>

<td>exponential time</td>

<td><a href="EXPTIME" title="EXPTIME">EXPTIME</a></td>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{{\textsf {poly}}(n)}}</annotation>

</semantics>

</math><img src="./3f1737189ba6047baf833987d0eb804cd1bbe9c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.483ex; height:2.843ex;" alt="{\displaystyle 2^{{\textsf {poly}}(n)}}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>

</semantics>

</math><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n^{2}}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n^{2}}}</annotation>

</semantics>

</math><img src="./e736acf2e0b9a29d97b91a1413af326c7175f117.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.212ex; height:3.009ex;" alt="{\displaystyle 2^{n^{2}}}" loading="lazy"></td>

<td>Solving <a href="Matrix_chain_multiplication" title="Matrix chain multiplication">matrix chain multiplication</a> via <a href="Brute-force_search" title="Brute-force search">brute-force search</a>

</td></tr>

<tr>

<td>double exponential time</td>

<td><a href="2-EXPTIME" title="2-EXPTIME">2-EXPTIME</a></td>

<msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{2^{{\textsf {poly}}(n)}}}</annotation>

</semantics>

</math><img src="./5a7ab6c705f33c1eaa63fbda1618514fe7cb50dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.512ex; height:3.176ex;" alt="{\displaystyle 2^{2^{{\textsf {poly}}(n)}}}" loading="lazy"></td>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{2^{n}}}</annotation>

</semantics>

</math><img src="./6bcc9417763ad5d68870290ddaa2ca025ffdaf85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.182ex; height:2.676ex;" alt="{\displaystyle 2^{2^{n}}}" loading="lazy"></td>

<td>Deciding the truth of a given statement in <a href="Presburger_arithmetic" title="Presburger arithmetic">Presburger arithmetic</a>

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Constant_time">Constant time</h2></div>

<div role="note" class="hatnote navigation-not-searchable">"Constant time" redirects here. For programming technique to avoid a timing attack, see <a href="Timing_attack#Avoidance" title="Timing attack">Timing attack § Avoidance</a>.</div>

An algorithm is said to be constant time (also written as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O(1)}</annotation>

</semantics>

</math><img src="./55a2cd47ca6554fafc21bbef3331256c7e1631ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\textstyle O(1)}" loading="lazy"> time) if the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle T(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle T(n)}</annotation>

</semantics>

</math><img src="./0b5ecab7146650b99bab59b6e97e228de0a4c61a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.84ex; height:2.843ex;" alt="{\textstyle T(n)}" loading="lazy"> (the complexity of the algorithm) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a> takes constant time as only one <a href="Instruction_(computer_science)" class="mw-redirect" title="Instruction (computer science)">operation</a> has to be performed to locate it. In a similar manner, finding the minimal value in an array sorted in ascending order; it is the first element. However, finding the minimal value in an unordered array is not a constant time operation as scanning over each <a href="Element_(math)" class="mw-redirect" title="Element (math)">element</a> in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O(n)}</annotation>

</semantics>

</math><img src="./e73234cd485b947e68d1d78823313db65ef226d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\textstyle O(n)}" loading="lazy"> time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time.

Despite the name "constant time", the running time does not have to be independent of the problem size, but an upper bound for the running time has to be independent of the problem size. For example, the task "exchange the values of a and b if necessary so that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle a\leq b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle a\leq b}</annotation>

</semantics>

</math><img src="./80bc3e45cdf18025be4beb90f84cf7b58cfcaf46.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.326ex; height:2.343ex;" alt="{\textstyle a\leq b}" loading="lazy">" is called constant time even though the time may depend on whether or not it is already true that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle a\leq b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle a\leq b}</annotation>

</semantics>

</math><img src="./80bc3e45cdf18025be4beb90f84cf7b58cfcaf46.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.326ex; height:2.343ex;" alt="{\textstyle a\leq b}" loading="lazy">. However, there is some constant t such that the time required is always at most t.

<div class="mw-heading mw-heading2"><h2 id="Logarithmic_time">Logarithmic time</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Logarithmic_growth" title="Logarithmic growth">Logarithmic growth</a></div>

An algorithm is said to take logarithmic time when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)=O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=O(\log n)}</annotation>

</semantics>

</math><img src="./298f88c665173713636b659403fdabaf115a15e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.275ex; height:2.843ex;" alt="{\displaystyle T(n)=O(\log n)}" loading="lazy">. Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{a}n}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{a}n}</annotation>

</semantics>

</math><img src="./2170c522b640ec2801a86c6c8bc66f9ae10e2c34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.855ex; height:2.676ex;" alt="{\displaystyle \log _{a}n}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{b}n}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{b}n}</annotation>

</semantics>

</math><img src="./52d9386c0be26d3cd2bc042a9856d4c3dd9a6f2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.691ex; height:2.676ex;" alt="{\displaystyle \log _{b}n}" loading="lazy"> are related by a <a href="Logarithmic_identities" class="mw-redirect" title="Logarithmic identities">constant multiplier</a>, and such a <a href="Big_O_notation#Multiplication_by_a_constant" title="Big O notation">multiplier is irrelevant</a> to big O classification, the standard usage for logarithmic-time algorithms is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"> regardless of the base of the logarithm appearing in the expression of T.

Algorithms taking logarithmic time are commonly found in operations on <a href="Binary_tree" title="Binary tree">binary trees</a> or when using <a href="Binary_search" title="Binary search">binary search</a>.

An <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"> algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when n increases. An algorithm that must access all elements of its input cannot take logarithmic time, as the time taken for reading an input of size n is of the order of n.

An example of logarithmic time is given by dictionary search. Consider a <a href="Dictionary_(data_structure)" class="mw-redirect" title="Dictionary (data structure)">dictionary</a> D which contains n entries, sorted in <a href="Alphabetical_order" title="Alphabetical order">alphabetical order</a>. We suppose that, for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq k\leq n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq k\leq n}</annotation>

</semantics>

</math><img src="./78ec00bc2eb99b403bee93def3c12ae87f1e3c3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.965ex; height:2.343ex;" alt="{\displaystyle 1\leq k\leq n}" loading="lazy">, one may access the kth entry of the dictionary in a constant time. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D(k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(k)}</annotation>

</semantics>

</math><img src="./f9c571e1520ae00f08fd58fb4d577491f592901a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.945ex; height:2.843ex;" alt="{\displaystyle D(k)}" loading="lazy"> denote this kth entry. Under these hypotheses, the test to see if a word w is in the dictionary may be done in logarithmic time: consider <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}">

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}</annotation>

</semantics>

</math><img src="./2edee9939c593f103c81f5819e73e1de781e6532.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:9.773ex; height:4.843ex;" alt="{\displaystyle D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor \;\rfloor }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lfloor \;\rfloor }</annotation>

</semantics>

</math><img src="./8d1d99deef81d9e1b3f2757b901042a218e2322a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.71ex; height:2.843ex;" alt="{\displaystyle \lfloor \;\rfloor }" loading="lazy"> denotes the <a href="Floor_function" class="mw-redirect" title="Floor function">floor function</a>. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}">

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}</annotation>

</semantics>

</math><img src="./32c796b219fc3540120b41a96017eda688c08b3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:14.535ex; height:4.843ex;" alt="{\displaystyle w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}" loading="lazy">--that is to say, the word w is exactly in the middle of the dictionary--then we are done. Else, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}">

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}</annotation>

</semantics>

</math><img src="./a3a6bdb8f549a2be360fb7331528fbf3c13bd288.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:14.535ex; height:4.843ex;" alt="{\displaystyle w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}" loading="lazy">--i.e., if the word w comes earlier in alphabetical order than the middle word of the whole dictionary--we continue the search in the same way in the left (i.e. earlier) half of the dictionary, and then again repeatedly until the correct word is found. Otherwise, if it comes after the middle word, continue similarly with the right half of the dictionary. This algorithm is similar to the method often used to find an entry in a paper dictionary. As a result, the search space within the dictionary decreases as the algorithm gets closer to the target word.

<div class="mw-heading mw-heading2"><h2 id="Polylogarithmic_time">Polylogarithmic time</h2></div>

An algorithm is said to run in <a href="Polylogarithmic_function" title="Polylogarithmic function">polylogarithmic</a> time if its time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)}</annotation>

</semantics>

</math><img src="./0be5a46684e1279c27414b285fa995f30407d002.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.84ex; height:2.843ex;" alt="{\displaystyle T(n)}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}}">

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}}</annotation>

</semantics>

</math><img src="./2d550792fa06ee0782c8d0e4b7668ede8f5388b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.555ex; height:3.343ex;" alt="{\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}}" loading="lazy"> for some constant k. Another way to write this is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log ^{k}n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{k}n)}</annotation>

</semantics>

</math><img src="./0261ca9897bad579fede1c3b4e2a20717b66fb5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.425ex; height:3.176ex;" alt="{\displaystyle O(\log ^{k}n)}" loading="lazy">.

For example, <a href="Matrix_chain_multiplication" title="Matrix chain multiplication">matrix chain ordering</a> can be solved in polylogarithmic time on a <a href="Parallel_random-access_machine" class="mw-redirect" title="Parallel random-access machine">parallel random-access machine</a>,<a href="#cite_note-7">[7]</a> and <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">a graph</a> can be <a href="Planarity_testing" title="Planarity testing">determined to be planar</a> in a <a href="Dynamic_connectivity" title="Dynamic connectivity">fully dynamic</a> way in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log ^{3}n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{3}n)}</annotation>

</semantics>

</math><img src="./a7f77c48b4c4e7b58b75244a9c512673896f6236.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.39ex; height:3.176ex;" alt="{\displaystyle O(\log ^{3}n)}" loading="lazy"> time per insert/delete operation.<a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Sub-linear_time">Sub-linear time</h2></div>

An algorithm is said to run in sub-linear time (often spelled sublinear time) if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)=o(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=o(n)}</annotation>

</semantics>

</math><img src="./cded9a3b1a3b5dc08a44b03338c5b54821c90a1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.27ex; height:2.843ex;" alt="{\displaystyle T(n)=o(n)}" loading="lazy">. In particular this includes algorithms with the time complexities defined above.

The specific term sublinear time algorithm commonly refers to randomized algorithms that sample a small fraction of their inputs and process them efficiently to <a href="Approximation_algorithm" title="Approximation algorithm">approximately</a> infer properties of the entire instance.<a href="#cite_note-9">[9]</a> This type of sublinear time algorithm is closely related to <a href="Property_testing" title="Property testing">property testing</a> and <a href="Statistics" title="Statistics">statistics</a>.

Other settings where algorithms can run in sublinear time include:

<ul><li><a href="Parallel_algorithm" title="Parallel algorithm">Parallel algorithms</a> that have linear or greater total <a href="Analysis_of_parallel_algorithms#Definitions" title="Analysis of parallel algorithms">work</a> (allowing them to read the entire input), but sub-linear <a href="Analysis_of_parallel_algorithms#Definitions" title="Analysis of parallel algorithms">depth</a>.</li>

<li>Algorithms that have <a href="Promise_problem" title="Promise problem">guaranteed assumptions</a> on the input structure. An important example are operations on <a href="Data_structures" class="mw-redirect" title="Data structures">data structures</a>, e.g. <a href="Binary_search_algorithm" class="mw-redirect" title="Binary search algorithm">binary search</a> in a sorted array.</li>

<li>Algorithms that search for local structure in the input, for example finding a local minimum in a 1-D array (can be solved in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(n))}</annotation>

</semantics>

</math><img src="./7d3f404959a75e486669fd7618e00046eb00bb24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.758ex; height:2.843ex;" alt="{\displaystyle O(\log(n))}" loading="lazy"> time using a variant of binary search).  A closely related notion is that of Local Computation Algorithms (LCA) where the algorithm receives a large input and queries to local information about some valid large output.<a href="#cite_note-10">[10]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Linear_time">Linear time</h2></div>

An algorithm is said to take linear time, or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> time, if its time complexity is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy">. Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constant c such that the running time is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle cn}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle cn}</annotation>

</semantics>

</math><img src="./7f0390269a433e7f1a987b5968c6229e43cd7a2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.402ex; height:1.676ex;" alt="{\displaystyle cn}" loading="lazy"> for every input of size n. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list, if the adding time is constant, or, at least, bounded by a constant.

Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input. Therefore, much research has been invested into discovering algorithms exhibiting linear time or, at least, nearly linear time. This research includes both software and hardware methods. There are several hardware technologies which exploit <a href="Parallel_computing" title="Parallel computing">parallelism</a> to provide this. An example is <a href="Content-addressable_memory" title="Content-addressable memory">content-addressable memory</a>. This concept of linear time is used in string matching algorithms such as the <a href="Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore string-search algorithm</a> and <a href="Ukkonen's_algorithm" title="Ukkonen's algorithm">Ukkonen's algorithm</a>.

<div class="mw-heading mw-heading2"><h2 id="Quasilinear_time"> Quasilinear time</h2></div>

An algorithm is said to run in quasilinear time (also referred to as log-linear time) if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)=O(n\log ^{k}n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=O(n\log ^{k}n)}</annotation>

</semantics>

</math><img src="./fb4711e3053ab6bb92b05c83b9e3037f1213784b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.145ex; height:3.176ex;" alt="{\displaystyle T(n)=O(n\log ^{k}n)}" loading="lazy"> for some positive constant k;<a href="#cite_note-11">[11]</a> linearithmic time is the case <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=1}</annotation>

</semantics>

</math><img src="./6c035ffa69b5bca8bf2d16c3da3aaad79a8bcbfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=1}" loading="lazy">.<a href="#cite_note-12">[12]</a> Using <a href="Soft_O_notation" class="mw-redirect" title="Soft O notation">soft O notation</a> these algorithms are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {O}}(n)}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tilde {O}}(n)}</annotation>

</semantics>

</math><img src="./725007a6715e12268a37cbbc5194302dfb7e69a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:3.176ex;" alt="{\displaystyle {\tilde {O}}(n)}" loading="lazy">. Quasilinear time algorithms are also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{1+\varepsilon })}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{1+\varepsilon })}</annotation>

</semantics>

</math><img src="./13194779a160ce780eee140bc714e50f6e2b62a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.076ex; height:3.176ex;" alt="{\displaystyle O(n^{1+\varepsilon })}" loading="lazy"> for every constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon >0}</annotation>

</semantics>

</math><img src="./e04ec3670b50384a3ce48aca42e7cc5131a06b12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;" alt="{\displaystyle \varepsilon >0}" loading="lazy"> and thus run faster than any polynomial time algorithm whose time bound includes a term <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{c}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{c}}</annotation>

</semantics>

</math><img src="./3a62b39da47c098d4cec1ac794318335b381c436.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.339ex; height:2.343ex;" alt="{\displaystyle n^{c}}" loading="lazy"> for any <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c>1}</annotation>

</semantics>

</math><img src="./bd1d6b5c226641ad3def8e65631f0eb463d9c67a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c>1}" loading="lazy">.

Algorithms which run in quasilinear time include:

<ul><li><a href="In-place_merge_sort" class="mw-redirect" title="In-place merge sort">In-place merge sort</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log ^{2}n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log ^{2}n)}</annotation>

</semantics>

</math><img src="./48c36489701bc8023db2f8d6bc809b14a7f8dd4e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.172ex; height:3.176ex;" alt="{\displaystyle O(n\log ^{2}n)}" loading="lazy"></li>

<li><a href="Quicksort" title="Quicksort">Quicksort</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy">, in its randomized version, has a running time that is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> in expectation on the worst-case input. Its non-randomized version has an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> running time only when considering average case complexity.</li>

<li><a href="Heapsort" title="Heapsort">Heapsort</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy">, <a href="Merge_sort" title="Merge sort">merge sort</a>, <a href="Introsort" title="Introsort">introsort</a>, binary tree sort, <a href="Smoothsort" title="Smoothsort">smoothsort</a>, <a href="Patience_sorting" title="Patience sorting">patience sorting</a>, etc. in the worst case</li>

<li><a href="Fast_Fourier_transform" title="Fast Fourier transform">Fast Fourier transforms</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"></li>

<li><a href="Monge_array" title="Monge array">Monge array</a> calculation, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"></li></ul>

In many cases, the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> running time is simply the result of performing a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (\log n)}</annotation>

</semantics>

</math><img src="./65bac5223de9c91eb3e89a032b5c51fd3041dc66.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.371ex; height:2.843ex;" alt="{\displaystyle \Theta (\log n)}" loading="lazy"> operation n times (for the notation, see <a href="Big_O_notation#Family_of_Bachmann–Landau_notations" title="Big O notation">Big O notation § Family of Bachmann–Landau notations</a>). For example, <a href="Binary_tree_sort" class="mw-redirect" title="Binary tree sort">binary tree sort</a> creates a <a href="Binary_tree" title="Binary tree">binary tree</a> by inserting each element of the n-sized array one by one. Since the insert operation on a <a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">self-balancing binary search tree</a> takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"> time, the entire algorithm takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> time.

<a href="Comparison_sort" title="Comparison sort">Comparison sorts</a> require at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n\log n)}</annotation>

</semantics>

</math><img src="./00663e988b37b064dbfe30791c3ad477907cc3a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.023ex; height:2.843ex;" alt="{\displaystyle \Omega (n\log n)}" loading="lazy"> comparisons in the worst case because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log(n!)=\Theta (n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log(n!)=\Theta (n\log n)}</annotation>

</semantics>

</math><img src="./74ad099d9cb60cd65e4234ed770a3923973eea8a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.074ex; height:2.843ex;" alt="{\displaystyle \log(n!)=\Theta (n\log n)}" loading="lazy">, by <a href="Stirling's_approximation" title="Stirling's approximation">Stirling's approximation</a>. They also frequently arise from the <a href="Recurrence_relation" title="Recurrence relation">recurrence relation</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}">

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}</annotation>

</semantics>

</math><img src="./b8cd0d7755d0bc79417b34d5a5ef603155de31d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:22.894ex; height:3.343ex;" alt="{\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Sub-quadratic_time">Sub-quadratic time</h2></div>

An <a href="Algorithm" title="Algorithm">algorithm</a> is said to be subquadratic time if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)=o(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=o(n^{2})}</annotation>

</semantics>

</math><img src="./b5a1fa201043da51e8f5fcadfc9922764da3408b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.325ex; height:3.176ex;" alt="{\displaystyle T(n)=o(n^{2})}" loading="lazy">.

For example, simple, comparison-based <a href="Sorting_algorithm" title="Sorting algorithm">sorting algorithms</a> are quadratic (e.g. <a href="Insertion_sort" title="Insertion sort">insertion sort</a>), but more advanced algorithms can be found that are subquadratic (e.g. <a href="Shell_sort" class="mw-redirect" title="Shell sort">shell sort</a>). No general-purpose sorts run in linear time, but the change from quadratic to sub-quadratic is of great practical importance.

<div class="mw-heading mw-heading2"><h2 id="Polynomial_time">Polynomial time</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="P_(complexity)" title="P (complexity)">P (complexity)</a></div>

An algorithm is said to be of polynomial time if its running time is <a href="Upper_bound" class="mw-redirect" title="Upper bound">upper bounded</a> by a <a href="Polynomial" title="Polynomial">polynomial</a> expression in the size of the input for the algorithm, that is, T(n) = O(nk) for some positive constant k.<a href="#cite_note-Sipser-1">[1]</a><a href="#cite_note-13">[13]</a> <a href="Decision_problem" title="Decision problem">Problems</a> for which a deterministic polynomial-time algorithm exists belong to the <a href="Complexity_class" title="Complexity class">complexity class</a> <a href="P_(complexity)" title="P (complexity)">P</a>, which is central in the field of <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>. <a href="Cobham's_thesis" title="Cobham's thesis">Cobham's thesis</a> states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".<a href="#cite_note-14">[14]</a>

Some examples of polynomial-time algorithms:

<ul><li>The <a href="Selection_sort" title="Selection sort">selection sort</a> sorting algorithm on n integers performs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle An^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle An^{2}}</annotation>

</semantics>

</math><img src="./2796e53b94e7bd410c057a6d425c4923ed580156.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.192ex; height:2.676ex;" alt="{\displaystyle An^{2}}" loading="lazy"> operations for some constant A. Thus it runs in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"> and is a polynomial-time algorithm.</li>

<li>All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.</li>

<li><a href="Maximum_matching" class="mw-redirect" title="Maximum matching">Maximum matchings</a> in <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graphs</a> can be found in polynomial time. In some contexts, especially in <a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">optimization</a>, one differentiates between <a href="Strongly-polynomial_time" title="Strongly-polynomial time">strongly polynomial time</a> and weakly polynomial time algorithms.</li></ul>

These two concepts are only relevant if the inputs to the algorithms consist of integers.

<div class="mw-heading mw-heading3"><h3 id="Complexity_classes">Complexity classes</h3></div>

The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes defined using polynomial time are the following.

<ul><li><a href="P_(complexity)" title="P (complexity)">P</a>: The <a href="Complexity_class" title="Complexity class">complexity class</a> of <a href="Decision_problem" title="Decision problem">decision problems</a> that can be solved on a <a href="Deterministic_Turing_machine" class="mw-redirect" title="Deterministic Turing machine">deterministic Turing machine</a> in polynomial time</li>

<li><a href="NP_(complexity)" title="NP (complexity)">NP</a>: The complexity class of decision problems that can be solved on a <a href="Non-deterministic_Turing_machine" class="mw-redirect" title="Non-deterministic Turing machine">non-deterministic Turing machine</a> in polynomial time</li>

<li><a href="ZPP_(complexity)" title="ZPP (complexity)">ZPP</a>: The complexity class of decision problems that can be solved with zero error on a <a href="Probabilistic_Turing_machine" title="Probabilistic Turing machine">probabilistic Turing machine</a> in polynomial time</li>

<li><a href="RP_(complexity)" title="RP (complexity)">RP</a>: The complexity class of decision problems that can be solved with 1-sided error on a probabilistic Turing machine in polynomial time.</li>

<li><a href="BPP_(complexity)" title="BPP (complexity)">BPP</a>: The complexity class of decision problems that can be solved with 2-sided error on a probabilistic Turing machine in polynomial time</li>

<li><a href="BQP" title="BQP">BQP</a>: The complexity class of decision problems that can be solved with 2-sided error on a <a href="Quantum_Turing_machine" title="Quantum Turing machine">quantum Turing machine</a> in polynomial time</li></ul>

P is the smallest time-complexity class on a deterministic machine which is <a href="Robustness_(computer_science)" title="Robustness (computer science)">robust</a> in terms of machine model changes. (For example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other.) Any given <a href="Abstract_machine" title="Abstract machine">abstract machine</a> will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.

<div class="mw-heading mw-heading2"><h2 id="Superpolynomial_time">Superpolynomial time</h2></div>

An algorithm is defined to take superpolynomial time if T(n) is not bounded above by any polynomial; that is, if ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)\not \in O(n^{c})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)\not \in O(n^{c})}</annotation>

</semantics>

</math><img src="./da9974f58cbc76c74b7157119dfdb63c04eb1d93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.602ex; height:2.843ex;" alt="{\displaystyle T(n)\not \in O(n^{c})}" loading="lazy">⁠ for every positive integer c.

For example, an algorithm that runs for 2n steps on an input of size n requires superpolynomial time (more specifically, exponential time).

An algorithm that uses exponential resources is clearly superpolynomial, but some algorithms are only very weakly superpolynomial. For example, the <a href="Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test" title="Adleman–Pomerance–Rumely primality test">Adleman–Pomerance–Rumely primality test</a> runs for nO(log log n) time on n-bit inputs; this grows faster than any polynomial for large enough n, but the input size must become impractically large before it cannot be dominated by a polynomial with small degree.

An algorithm that requires superpolynomial time lies outside the <a href="Complexity_class" title="Complexity class">complexity class</a> <a href="P_(complexity)" title="P (complexity)">P</a>. <a href="Cobham's_thesis" title="Cobham's thesis">Cobham's thesis</a> posits that these algorithms are impractical, and in many cases they are. Since the <a href="P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a> is unresolved, it is unknown whether <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a> problems require superpolynomial time.

<div class="mw-heading mw-heading2"><h2 id="Quasi-polynomial_time">Quasi-polynomial time</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Quasi-polynomial_time" title="Quasi-polynomial time">Quasi-polynomial time</a></div>

Quasi-polynomial time algorithms are algorithms whose running time exhibits <a href="Quasi-polynomial_growth" title="Quasi-polynomial growth">quasi-polynomial growth</a>, a type of behavior that may be slower than polynomial time but yet is significantly faster than <a href="Exponential_time" class="mw-redirect" title="Exponential time">exponential time</a>. The worst case running time of a quasi-polynomial time algorithm is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{O(\log ^{c}n)}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{O(\log ^{c}n)}}</annotation>

</semantics>

</math><img src="./8bf734f7fea354217d29a8bc1a007044ab520aae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.145ex; height:2.843ex;" alt="{\displaystyle 2^{O(\log ^{c}n)}}" loading="lazy"> for some fixed <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c>0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c>0}</annotation>

</semantics>

</math><img src="./2ba126f626d61752f62eaacaf11761a54de4dc84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c>0}" loading="lazy">. When <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=1}</annotation>

</semantics>

</math><img src="./3e3467f9e219a5ea38a30da5c3a02c2c23f61a79.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c=1}" loading="lazy"> this gives polynomial time, and for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c<1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c<1}</annotation>

</semantics>

</math><img src="./d8f310fc940b3622eefb2bb82bb2cb2a049a60c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c<1}" loading="lazy"> it gives sub-linear time.

There are some problems for which we know quasi-polynomial time algorithms, but no polynomial time algorithm is known. Such problems arise in approximation algorithms; a famous example is the directed <a href="Steiner_tree_problem" title="Steiner tree problem">Steiner tree problem</a>, for which there is a quasi-polynomial time approximation algorithm achieving an approximation factor of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log ^{3}n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{3}n)}</annotation>

</semantics>

</math><img src="./a7f77c48b4c4e7b58b75244a9c512673896f6236.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.39ex; height:3.176ex;" alt="{\displaystyle O(\log ^{3}n)}" loading="lazy"> (n being the number of vertices), but showing the existence of such a polynomial time algorithm is an open problem.

Other computational problems with quasi-polynomial time solutions but no known polynomial time solution include the <a href="Planted_clique" title="Planted clique">planted clique</a> problem in which the goal is to <a href="Clique_problem" title="Clique problem">find a large clique</a> in the union of a clique and a <a href="Random_graph" title="Random graph">random graph</a>. Although quasi-polynomially solvable, it has been conjectured that the planted clique problem has no polynomial time solution; this planted clique conjecture has been used as a <a href="Computational_hardness_assumption" title="Computational hardness assumption">computational hardness assumption</a> to prove the difficulty of several other problems in computational <a href="Game_theory" title="Game theory">game theory</a>, <a href="Property_testing" title="Property testing">property testing</a>, and <a href="Machine_learning" title="Machine learning">machine learning</a>.<a href="#cite_note-15">[15]</a>

The complexity class QP consists of all problems that have quasi-polynomial time algorithms. It can be defined in terms of <a href="DTIME" title="DTIME">DTIME</a> as follows.<a href="#cite_note-16">[16]</a>

</mstyle>

</mrow>

</mrow>

</munder>

<mtext>DTIME</mtext>

</mstyle>

</mrow>

<mrow>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n}\right)}</annotation>

</semantics>

</math><img src="./efc34b706aa344b0652e533568b621f576904089.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:26.653ex; height:6.176ex;" alt="{\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n}\right)}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Relation_to_NP-complete_problems">Relation to NP-complete problems</h3></div>

In complexity theory, the unsolved <a href="P_versus_NP" class="mw-redirect" title="P versus NP">P versus NP</a> problem asks if all problems in NP have polynomial-time algorithms. All the best-known algorithms for <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a> problems like 3SAT etc. take exponential time. Indeed, it is conjectured for many natural NP-complete problems that they do not have sub-exponential time algorithms. Here "sub-exponential time" is taken to mean the second definition presented below. (On the other hand, many graph problems represented in the natural way by adjacency matrices are solvable in subexponential time simply because the size of the input is the square of the number of vertices.) This conjecture (for the k-SAT problem) is known as the <a href="Exponential_time_hypothesis" title="Exponential time hypothesis">exponential time hypothesis</a>.<a href="#cite_note-ETH-17">[17]</a> Since it is conjectured that NP-complete problems do not have quasi-polynomial time algorithms, some inapproximability results in the field of <a href="Approximation_algorithms" class="mw-redirect" title="Approximation algorithms">approximation algorithms</a> make the assumption that NP-complete problems do not have quasi-polynomial time algorithms. For example, see the known inapproximability results for the <a href="Set_cover" class="mw-redirect" title="Set cover">set cover</a> problem.

<div class="mw-heading mw-heading2"><h2 id="Sub-exponential_time">Sub-exponential time</h2></div>

The term <a href="Infra-exponential" title="Infra-exponential">sub-exponential</a> time is used to express that the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential. In this sense, problems that have sub-exponential time algorithms are somewhat more tractable than those that only have exponential algorithms. The precise definition of "sub-exponential" is not generally agreed upon,<a href="#cite_note-18">[18]</a> however the two most widely used are below.

<div class="mw-heading mw-heading3"><h3 id="First_definition">First definition</h3></div>

A problem is said to be sub-exponential time solvable if it can be solved in running times whose logarithms grow smaller than any given polynomial. More precisely, a problem is in sub-exponential time if for every ε > 0 there exists an algorithm which solves the problem in time O(2nε). The set of all such problems is the complexity class SUBEXP which can be defined in terms of <a href="DTIME" title="DTIME">DTIME</a> as follows.<a href="#cite_note-bpp-6">[6]</a><a href="#cite_note-19">[19]</a><a href="#cite_note-20">[20]</a><a href="#cite_note-21">[21]</a>

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\textsf {SUBEXP}}=\bigcap _{\varepsilon >0}{\textsf {DTIME}}\left(2^{n^{\varepsilon }}\right)}">

<mtext mathvariant="sans-serif">SUBEXP</mtext>

</mrow>

</mrow>

</munder>

<mtext mathvariant="sans-serif">DTIME</mtext>

</mrow>

<mrow>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\textsf {SUBEXP}}=\bigcap _{\varepsilon >0}{\textsf {DTIME}}\left(2^{n^{\varepsilon }}\right)}</annotation>

</semantics>

</math><img src="./50431aafa01d7707f0494d10efa56dd39499155f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:28.876ex; height:6.009ex;" alt="{\displaystyle {\textsf {SUBEXP}}=\bigcap _{\varepsilon >0}{\textsf {DTIME}}\left(2^{n^{\varepsilon }}\right)}" loading="lazy"></dd></dl>

This notion of sub-exponential is non-uniform in terms of ε in the sense that ε is not part of the input and each ε may have its own algorithm for the problem.

<div class="mw-heading mw-heading3"><h3 id="Second_definition">Second definition</h3></div>

Some authors define sub-exponential time as running times in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{o(n)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{o(n)}}</annotation>

</semantics>

</math><img src="./98ee27d18f582367c1c737ddc1c3380a92c93c0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.458ex; height:2.843ex;" alt="{\displaystyle 2^{o(n)}}" loading="lazy">.<a href="#cite_note-ETH-17">[17]</a><a href="#cite_note-22">[22]</a><a href="#cite_note-23">[23]</a> This definition allows larger running times than the first definition of sub-exponential time. An example of such a sub-exponential time algorithm is the best-known classical algorithm for integer factorization, the <a href="General_number_field_sieve" title="General number field sieve">general number field sieve</a>, which runs in time about <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{{\tilde {O}}(n^{1/3})}}">

<msup>

<mover>

</mover>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{{\tilde {O}}(n^{1/3})}}</annotation>

</semantics>

</math><img src="./30d319f41f6fb8ab309bf15ad8a64c870cb52021.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.08ex; height:3.176ex;" alt="{\displaystyle 2^{{\tilde {O}}(n^{1/3})}}" loading="lazy">, where the length of the input is n. Another example was the <a href="Graph_isomorphism_problem" title="Graph isomorphism problem">graph isomorphism problem</a>, which the best known algorithm from 1982 to 2016 solved in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{O\left({\sqrt {n\log n}}\right)}}">

<msup>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{O\left({\sqrt {n\log n}}\right)}}</annotation>

</semantics>

</math><img src="./421e4106c1d0cbf0b63861e4473c479865a04a07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.646ex; height:3.009ex;" alt="{\displaystyle 2^{O\left({\sqrt {n\log n}}\right)}}" loading="lazy">. However, at <a href="Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">STOC</a> 2016 a quasi-polynomial time algorithm was presented.<a href="#cite_note-24">[24]</a>

It makes a difference whether the algorithm is allowed to be sub-exponential in the size of the instance, the number of vertices, or the number of edges. In <a href="Parameterized_complexity" title="Parameterized complexity">parameterized complexity</a>, this difference is made explicit by considering pairs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (L,k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (L,k)}</annotation>

</semantics>

</math><img src="./60912d6e9f29e343e9e77d28e3a19ede88d9d655.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.637ex; height:2.843ex;" alt="{\displaystyle (L,k)}" loading="lazy"> of <a href="Decision_problem" title="Decision problem">decision problems</a> and parameters k. SUBEPT is the class of all parameterized problems that run in time sub-exponential in k and polynomial in the input size n:<a href="#cite_note-25">[25]</a>

<mtext mathvariant="sans-serif">SUBEPT</mtext>

</mrow>

<mtext mathvariant="sans-serif">DTIME</mtext>

</mrow>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\textsf {SUBEPT}}={\textsf {DTIME}}\left(2^{o(k)}\cdot {\textsf {poly}}(n)\right).}</annotation>

</semantics>

</math><img src="./9dbccad17791a606fd857ddea9164b23c2f4687c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:36.725ex; height:4.843ex;" alt="{\displaystyle {\textsf {SUBEPT}}={\textsf {DTIME}}\left(2^{o(k)}\cdot {\textsf {poly}}(n)\right).}" loading="lazy"></dd></dl>

More precisely, SUBEPT is the class of all parameterized problems <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (L,k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (L,k)}</annotation>

</semantics>

</math><img src="./60912d6e9f29e343e9e77d28e3a19ede88d9d655.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.637ex; height:2.843ex;" alt="{\displaystyle (L,k)}" loading="lazy"> for which there is a <a href="Computable_function" title="Computable function">computable function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\mathbb {N} \to \mathbb {N} }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\mathbb {N} \to \mathbb {N} }</annotation>

</semantics>

</math><img src="./dfa847e103c9e2e5075b1b510f67aad8ceae9349.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.186ex; height:2.509ex;" alt="{\displaystyle f:\mathbb {N} \to \mathbb {N} }" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\in o(k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\in o(k)}</annotation>

</semantics>

</math><img src="./ea31b6df475b663254eeea2570f974d8ce662741.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.267ex; height:2.843ex;" alt="{\displaystyle f\in o(k)}" loading="lazy"> and an algorithm that decides L in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{f(k)}\cdot {\textsf {poly}}(n)}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{f(k)}\cdot {\textsf {poly}}(n)}</annotation>

</semantics>

</math><img src="./683d5625f307b5169057927f8340fd937f9c08a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.31ex; height:3.343ex;" alt="{\displaystyle 2^{f(k)}\cdot {\textsf {poly}}(n)}" loading="lazy">.

<div class="mw-heading mw-heading4"><h4 id="Exponential_time_hypothesis">Exponential time hypothesis</h4></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Exponential_time_hypothesis" title="Exponential time hypothesis">Exponential time hypothesis</a></div>

The exponential time hypothesis (ETH) is that <a href="3SAT" class="mw-redirect" title="3SAT">3SAT</a>, the satisfiability problem of Boolean formulas in <a href="Conjunctive_normal_form" title="Conjunctive normal form">conjunctive normal form</a> with at most three literals per clause and with n variables, cannot be solved in time 2o(n). More precisely, the hypothesis is that there is some absolute constant c > 0 such that 3SAT cannot be decided in time 2cn by any deterministic Turing machine. With m denoting the number of clauses, ETH is equivalent to the hypothesis that kSAT cannot be solved in time 2o(m) for any integer k ≥ 3.<a href="#cite_note-26">[26]</a> The exponential time hypothesis implies <a href="P_%E2%89%A0_NP" class="mw-redirect" title="P ≠ NP">P ≠ NP</a>.

<div class="mw-heading mw-heading2"><h2 id="Exponential_time">Exponential time</h2></div>

An algorithm is said to be exponential time, if T(n) is upper bounded by 2poly(n), where poly(n) is some polynomial in n. More formally, an algorithm is exponential time if T(n) is bounded by O(2nk) for some constant k. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as <a href="EXP" class="mw-redirect" title="EXP">EXP</a>.

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mtext mathvariant="sans-serif">DTIME</mtext>

</mrow>

<mrow>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\textsf {EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\textsf {DTIME}}\left(2^{n^{c}}\right)}</annotation>

</semantics>

</math><img src="./0ec19601cd7cb879544f80f1346568d4a365ccd0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:25.721ex; height:6.343ex;" alt="{\displaystyle {\textsf {EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\textsf {DTIME}}\left(2^{n^{c}}\right)}" loading="lazy"></dd></dl>

Sometimes, exponential time is used to refer to algorithms that have T(n) = 2O(n), where the exponent is at most a linear function of n. This gives rise to the complexity class <a href="E_(complexity)" title="E (complexity)">E</a>.

</mrow>

</mrow>

</munder>

<mtext mathvariant="sans-serif">DTIME</mtext>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\textsf {E}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{cn}\right)}</annotation>

</semantics>

</math><img src="./0bf6e95c5536ea5b94aadc0a37801d241c22067e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:20.486ex; height:5.676ex;" alt="{\displaystyle {\textsf {E}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{cn}\right)}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Factorial_time">Factorial time</h2></div>

An algorithm is said to be factorial time if T(n) is upper bounded by the <a href="Factorial_function" class="mw-redirect" title="Factorial function">factorial function</a> n!. Factorial time is a subset of exponential time (EXP) because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<mrow>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)}</annotation>

</semantics>

</math><img src="./7d00a62e76b74b7da06d90644aa16abd7b7c95f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:29.921ex; height:4.843ex;" alt="{\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon >0}</annotation>

</semantics>

</math><img src="./568095ad3924314374a5ab68fae17343661f2a71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.205ex; height:2.176ex;" alt="{\displaystyle \epsilon >0}" loading="lazy">. However, it is not a subset of E.

An example of an algorithm that runs in factorial time is <a href="Bogosort" title="Bogosort">bogosort</a>, a notoriously inefficient sorting algorithm based on <a href="Trial_and_error" title="Trial and error">trial and error</a>. Bogosort sorts a list of n items by repeatedly <a href="Shuffling" title="Shuffling">shuffling</a> the list until it is found to be sorted. In the average case, each pass through the bogosort algorithm will examine one of the n! orderings of the n items. If the items are distinct, only one such ordering is sorted. Bogosort shares patrimony with the <a href="Infinite_monkey_theorem" title="Infinite monkey theorem">infinite monkey theorem</a>.

<div class="mw-heading mw-heading2"><h2 id="Double_exponential_time">Double exponential time</h2></div>

An algorithm is said to be <a href="Double_exponential_function" title="Double exponential function">double exponential</a> time if T(n) is upper bounded by 22poly(n), where poly(n) is some polynomial in n. Such algorithms belong to the complexity class <a href="2-EXPTIME" title="2-EXPTIME">2-EXPTIME</a>.

<mtext mathvariant="sans-serif">2-EXPTIME</mtext>

</mrow>

</mrow>

</munder>

<mtext mathvariant="sans-serif">DTIME</mtext>

</mrow>

<mrow>

<msup>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\textsf {2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{2^{n^{c}}}\right)}</annotation>

</semantics>

</math><img src="./47dd0dfedf878a1b07638251d89a4537e48c9475.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:32.876ex; height:6.176ex;" alt="{\displaystyle {\textsf {2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{2^{n^{c}}}\right)}" loading="lazy"></dd></dl>

Well-known double exponential time algorithms include:

<ul><li>Decision procedures for <a href="Presburger_arithmetic" title="Presburger arithmetic">Presburger arithmetic</a></li>

<li>Computing a <a href="Gr%C3%B6bner_basis" title="Gröbner basis">Gröbner basis</a> (in the worst case<a href="#cite_note-27">[27]</a>)</li>

<li><a href="Quantifier_elimination" title="Quantifier elimination">Quantifier elimination</a> on <a href="Real_closed_field" title="Real closed field">real closed fields</a> takes at least double exponential time,<a href="#cite_note-28">[28]</a> and can be done in this time.<a href="#cite_note-29">[29]</a></li></ul>

<ul><li><a href="L-notation" title="L-notation">L-notation</a></li>

<li><a href="Space_complexity" title="Space complexity">Space complexity</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 33em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSipser2006" class="citation book cs1"><a href="Michael_Sipser" title="Michael Sipser">Sipser, Michael</a> (2006). Introduction to the Theory of Computation. Course Technology Inc. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-619-21764-2</bdi>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFMehlhornNaher1990" class="citation journal cs1"><a href="Kurt_Mehlhorn" title="Kurt Mehlhorn">Mehlhorn, Kurt</a>; Naher, Stefan (1990). "Bounded ordered dictionaries in O(log log N) time and O(n) space". <a href="Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a>. 35 (4): 183–189. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2890%2990022-P">10.1016/0020-0190(90)90022-P</a>.</cite>

</li>

<li id="cite_note-tao-aks-3"><a href="#cite_ref-tao-aks_3-0">^</a> <cite id="CITEREFTao2010" class="citation book cs1"><a href="Terence_Tao" title="Terence Tao">Tao, Terence</a> (2010). <a rel="nofollow" class="external text" href="https://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/">"1.11 The AKS primality test"</a>. An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics. Vol. 117. Providence, RI: American Mathematical Society. pp. 82–86. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fgsm%2F117">10.1090/gsm/117</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8218-5280-4</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2780010">2780010</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFLenstraPomerance2019" class="citation journal cs1"><a href="Hendrik_Lenstra" title="Hendrik Lenstra">Lenstra, H. W. Jr.</a>; <a href="Carl_Pomerance" title="Carl Pomerance">Pomerance, Carl</a> (2019). <a rel="nofollow" class="external text" href="https://math.dartmouth.edu/~carlp/aks111216.pdf">"Primality testing with Gaussian periods"</a> (PDF). <a href="Journal_of_the_European_Mathematical_Society" title="Journal of the European Mathematical Society">Journal of the European Mathematical Society</a>. 21 (4): 1229–1269. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4171%2FJEMS%2F861">10.4171/JEMS/861</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/21.11116%2F0000-0005-717D-0">21.11116/0000-0005-717D-0</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3941463">3941463</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:127807021">127807021</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFCalude,_Cristian_S._and_Jain,_Sanjay_and_Khoussainov,_Bakhadyr_and_Li,_Wei_and_Stephan,_Frank2017" class="citation book cs1">Calude, Cristian S. and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Stephan, Frank (2017). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3055399.3055409">"Deciding parity games in quasipolynomial time"</a>. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. pp. 252–263. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3055399.3055409">10.1145/3055399.3055409</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2292%2F31757">2292/31757</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781450345286</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:30338402">30338402</a>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-bpp-6">^ <a href="#cite_ref-bpp_6-0">a</a> <a href="#cite_ref-bpp_6-1">b</a> <cite id="CITEREFBabaiFortnowNisanWigderson1993" class="citation journal cs1"><a href="L%C3%A1szl%C3%B3_Babai" title="László Babai">Babai, László</a>; <a href="Lance_Fortnow" title="Lance Fortnow">Fortnow, Lance</a>; <a href="Noam_Nisan" title="Noam Nisan">Nisan, N.</a>; <a href="Avi_Wigderson" title="Avi Wigderson">Wigderson, Avi</a> (1993). "BPP has subexponential time simulations unless EXPTIME has publishable proofs". Computational Complexity. 3 (4). Berlin, New York: <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>: 307–318. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01275486">10.1007/BF01275486</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14802332">14802332</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFBradfordRawlinsShannon1998" class="citation journal cs1">Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998). "Efficient matrix chain ordering in polylog time". <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>. 27 (2): 466–490. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539794270698">10.1137/S0097539794270698</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1616556">1616556</a>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFHolmRotenberg2020" class="citation conference cs1">Holm, Jacob; Rotenberg, Eva (2020). "Fully-dynamic planarity testing in polylogarithmic time". In Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; <a href="Julia_Chuzhoy" title="Julia Chuzhoy">Chuzhoy, Julia</a> (eds.). Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. Association for Computing Machinery. pp. 167–180. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1911.03449">1911.03449</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3357713.3384249">10.1145/3357713.3384249</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-6979-4</bdi>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFKumarRubinfeld2003" class="citation journal cs1">Kumar, Ravi; <a href="Ronitt_Rubinfeld" title="Ronitt Rubinfeld">Rubinfeld, Ronitt</a> (2003). <a rel="nofollow" class="external text" href="http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/kumarR-survey.pdf">"Sublinear time algorithms"</a> (PDF). <a href="SIGACT_News" class="mw-redirect" title="SIGACT News">SIGACT News</a>. 34 (4): 57–67. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F954092.954103">10.1145/954092.954103</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:65359">65359</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFRubinfeld2019" class="citation book cs1"><a href="Ronitt_Rubinfeld" title="Ronitt Rubinfeld">Rubinfeld, Ronitt</a> (2019). "Local Computation Algorithms". Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. p. 3. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3293611.3331587">10.1145/3293611.3331587</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-6217-7</bdi>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFNaikReganSivakumar1995" class="citation journal cs1">Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). <a rel="nofollow" class="external text" href="http://www.cse.buffalo.edu/~regan/papers/pdf/NRS95.pdf">"On quasilinear-time complexity theory"</a> (PDF). <a href="Theoretical_Computer_Science_(journal)" title="Theoretical Computer Science (journal)">Theoretical Computer Science</a>. 148 (2): 325–349. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2895%2900031-Q">10.1016/0304-3975(95)00031-Q</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1355592">1355592</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFSedgewickWayne2011" class="citation book cs1">Sedgewick, Robert; Wayne, Kevin (2011). <a rel="nofollow" class="external text" href="https://algs4.cs.princeton.edu/home/">Algorithms</a> (4th ed.). Pearson Education. p. 186.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFPapadimitriou1994" class="citation book cs1"><a href="Christos_H._Papadimitriou" class="mw-redirect" title="Christos H. Papadimitriou">Papadimitriou, Christos H.</a> (1994). Computational complexity. Reading, Mass.: Addison-Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-53082-1</bdi>.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFCobham1965" class="citation book cs1"><a href="Alan_Cobham_(mathematician)" title="Alan Cobham (mathematician)">Cobham, Alan</a> (1965). "The intrinsic computational difficulty of functions". Proc. Logic, Methodology, and Philosophy of Science II. North Holland.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFBravermanKun-KoRubinsteinWeinstein2017" class="citation conference cs1"><a href="Mark_Braverman_(mathematician)" title="Mark Braverman (mathematician)">Braverman, Mark</a>; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omri (2017). "ETH hardness for densest-k-subgraph with perfect completeness". In Klein, Philip N. (ed.). Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19. Society for Industrial and Applied Mathematics. pp. 1326–1341. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1504.08352">1504.08352</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9781611974782.86">10.1137/1.9781611974782.86</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-61197-478-2</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3627815">3627815</a>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <a href="Complexity_Zoo" class="mw-redirect" title="Complexity Zoo">Complexity Zoo</a>: <a rel="nofollow" class="external text" href="https://complexityzoo.net/Complexity_Zoo:Q#qp">Class QP: Quasipolynomial-Time</a>

</li>

<li id="cite_note-ETH-17">^ <a href="#cite_ref-ETH_17-0">a</a> <a href="#cite_ref-ETH_17-1">b</a> <cite id="CITEREFImpagliazzoPaturi2001" class="citation journal cs1"><a href="Russell_Impagliazzo" title="Russell Impagliazzo">Impagliazzo, Russell</a>; Paturi, Ramamohan (2001). <a rel="nofollow" class="external text" href="https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf">"On the complexity of k-SAT"</a> (PDF). <a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a>. 62 (2): 367–375. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.2000.1727">10.1006/jcss.2000.1727</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1820597">1820597</a>.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFAaronson,_Scott2009" class="citation web cs1">Aaronson, Scott (5 April 2009). <a rel="nofollow" class="external text" href="http://scottaaronson.com/blog/?p=394">"A not-quite-exponential dilemma"</a>. Shtetl-Optimized. Retrieved 2 December 2009.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <a href="Complexity_Zoo" class="mw-redirect" title="Complexity Zoo">Complexity Zoo</a>: <a rel="nofollow" class="external text" href="https://complexityzoo.net/Complexity_Zoo:S#subexp">Class SUBEXP: Deterministic Subexponential-Time</a>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFMoser2003" class="citation conference cs1">Moser, P. (2003). "Baire's Categories on Small Complexity Classes". In Andrzej Lingas; Bengt J. Nilsson (eds.). Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings. <a href="Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">Lecture Notes in Computer Science</a>. Vol. 2751. Berlin, New York: Springer-Verlag. pp. 333–342. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-45077-1_31">10.1007/978-3-540-45077-1_31</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-40543-6</bdi>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFMiltersen2001" class="citation book cs1">Miltersen, P.B. (2001). "Derandomizing Complexity Classes". Handbook of Randomized Computing. Combinatorial Optimization. Vol. 9. Kluwer Academic Pub. p. 843. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4615-0013-1_19">10.1007/978-1-4615-0013-1_19</a> (inactive 21 July 2025). <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4613-4886-3</bdi>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: DOI inactive as of July 2025 (link)

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFKuperberg2005" class="citation journal cs1">Kuperberg, Greg (2005). "A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem". SIAM Journal on Computing. 35 (1). Philadelphia: 188. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0302112">quant-ph/0302112</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2Fs0097539703436345">10.1137/s0097539703436345</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1095-7111">1095-7111</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15965140">15965140</a>.</cite>

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <cite id="CITEREFOded_Regev2004" class="citation arxiv cs1">Oded Regev (2004). "A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0406151v1">quant-ph/0406151v1</a>.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFGroheNeuen2021" class="citation book cs1">Grohe, Martin; Neuen, Daniel (2021). "Recent advances on the graph isomorphism problem". In Dabrowski, Konrad K.; Gadouleau, Maximilien; Georgiou, Nicholas; Johnson, Matthew; Mertzios, George B.; Paulusma, Daniël (eds.). Surveys in combinatorics 2021. London Mathematical Society Lecture Note Series. Vol. 470. Cambridge University Press. pp. 187–234. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2011.01366">2011.01366</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-009-01888-3</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=4273431">4273431</a>.</cite>

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFFlumGrohe2006" class="citation book cs1">Flum, Jörg; <a href="Martin_Grohe" title="Martin Grohe">Grohe, Martin</a> (2006). <a rel="nofollow" class="external text" href="https://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0">Parameterized Complexity Theory</a>. Springer. p. 417. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-29952-3</bdi>.</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFImpagliazzoPaturiZane2001" class="citation journal cs1"><a href="Russell_Impagliazzo" title="Russell Impagliazzo">Impagliazzo, R.</a>; Paturi, R.; Zane, F. (2001). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.2001.1774">"Which problems have strongly exponential complexity?"</a>. <a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a>. 63 (4): 512–530. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.2001.1774">10.1006/jcss.2001.1774</a>.</cite>

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <cite id="CITEREFMayrMeyer1982" class="citation journal cs1"><a href="Ernst_Mayr_(computer_scientist)" title="Ernst Mayr (computer scientist)">Mayr, Ernst W.</a>; <a href="Albert_R._Meyer" title="Albert R. Meyer">Meyer, Albert R.</a> (1982). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0001-8708%2882%2990048-2">"The complexity of the word problems for commutative semigroups and polynomial ideals"</a>. <a href="Advances_in_Mathematics" title="Advances in Mathematics">Advances in Mathematics</a>. 46 (3): 305–329. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0001-8708%2882%2990048-2">10.1016/0001-8708(82)90048-2</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1721.1%2F149010">1721.1/149010</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0683204">0683204</a>.</cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFDavenportHeintz1988" class="citation journal cs1"><a href="James_H._Davenport" title="James H. Davenport">Davenport, James H.</a>; <a href="Joos_Ulrich_Heintz" title="Joos Ulrich Heintz">Heintz, Joos</a> (1988). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0747-7171%2888%2980004-X">"Real quantifier elimination is doubly exponential"</a>. <a href="Journal_of_Symbolic_Computation" title="Journal of Symbolic Computation">Journal of Symbolic Computation</a>. 5 (1–2): 29–35. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0747-7171%2888%2980004-X">10.1016/S0747-7171(88)80004-X</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0949111">0949111</a>.</cite>

</li>

<li id="cite_note-29"><a href="#cite_ref-29">^</a> <cite id="CITEREFCollins1975" class="citation conference cs1"><a href="George_E._Collins" title="George E. Collins">Collins, George E.</a> (1975). "Quantifier elimination for real closed fields by cylindrical algebraic decomposition". In Brakhage, H. (ed.). Automata Theory and Formal Languages: 2nd GI Conference, Kaiserslautern, May 20–23, 1975. Lecture Notes in Computer Science. Vol. 33. Springer. pp. 134–183. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-07407-4_17">10.1007/3-540-07407-4_17</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-07407-6</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0403962">0403962</a>.</cite>

</li>

</ol></div>

</div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-21" href="https://en.wikipedia.org/wiki/?title=Time_complexity&oldid=1301705755">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>